package arithmetic.someAlgorithm;
/**
 * 一个数组中有一个数的个数超过数组的一半，写一个算法找到这个数,方法二
 * @author lidd
 *
 */
public class FindNum2 {

	public static void main(String[] args) {
		int[] arr = new int[] { 1, 2, 3, 3, 3, 5, 7, 3, 3 };
		int num = MoreHalf(arr);
		System.out.println(num);
	}

	public static int MoreHalf(int[] nums) {
		int result = nums[0];
		int flag = 1;
		if (nums.length == 0)
			return -1;
		for (int i = 1; i < nums.length; i++) {
			if (flag == 0) {
				result = nums[i];
				flag = 1;
				continue;
			}
			if (result == nums[i])
				flag++;
			else
				flag--;
		}
		flag = 0;
		for (int i = 0; i < nums.length; i++) {
			if (result == nums[i])
				flag++;
		}
		if (flag > nums.length / 2)
			return result;
		return 0;
	}
}
